package BFS_DFS;

import java.util.Scanner;

public class DFS全排列 {
    static int n;//个数
    static int[] a;//数组
    static int[] b;//当前数组
    static boolean[] vis;//判断是否用过

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        a=new int[n];
        b=new int[n];
        vis=new boolean[n];
        for (int i = 0; i < n; i++) {
            a[i]=i+1;
        }
        dfs(0);
    }

    static void dfs(int step){
        if(step==n){
            for (int i = 0; i < n; i++) {
                System.out.print(b[i]);
            }
            System.out.println();
            return;
        }
        for (int i = 0; i < n; i++) {
            if(!vis[i]){
                b[step]=a[i];
                vis[i]=true;
                dfs(step+1);
                vis[i]=false;
            }
        }
    }
}


/*
有n名同学，要选k人排一列拍照，请输出所以可能排列方式。
public class 组合排列 {
    static int n; // 总人数
    static int k; // 选择的人数
    static int[] a;
    static int[] b;
    static boolean[] vis;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        vis = new boolean[n];
        a = new int[n]; // 存储学生编号
        b = new int[k]; // 当前排列

        for (int i = 0; i < n; i++) {
            a[i] = i+1;
        }
        dfs(0);
    }

    static void dfs(int step) {
        if (step == k) { // 当step等于k时，表示已得到一个排列
            for (int i = 0; i < k; i++) {
                System.out.print(b[i] + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                b[step] = a[i];
                vis[i] = true;
                dfs(step + 1);
                vis[i] = false;
            }
        }
    }
 */
